﻿/**
 * @file tree.h
 * @author septem (jsm920@outlook.com)
 * @brief 实现一个二叉树数据结构 btree_t和实现一个树结构 tree_t 。
 * @version 0.0.1
 * @date 2024-12-07
 * 
 * @copyright Copyright (c) 2024
 * 
 */
#ifndef _HEAD_TREE_
#define _HEAD_TREE_
#if defined(_WIN32) && defined(_MSC_VER)
// #pragma execution_character_set("utf-8")
#define WIN32_LEAN_AND_MEAN // 预处理器宏定义，它告诉编译器仅包含Windows SDK中最常用的函数和数据类型，从而减小编译时间和生成的可执行文件大小。
#include <stdio.h>
#elif defined(__linux__)
#include <stdio.h>
#endif

#ifndef roundup
#if defined(_WIN32) && defined(_MSC_VER)
//对 x 向上取 y 的整数倍
#define  roundup(x, y) ((((x) + ((y) - 1)) / (y)) * (y))
#elif defined(__linux__)
//对 x 向上取 y 的整数倍
#define  roundup(x, y) 			    \
({							        \
	typeof(y) __y = y;				\
	(((x) + (__y - 1)) / __y) * __y;\
})
#endif
#endif

#define LEVEL_ORDER_TRAVERSAL 32 // 广度优先遍历算法(Breadth First Search or BFS or Level order traversal)初始队列大小

/**
 * @brief 二叉数的结点
 * 
 */
typedef struct btreenode_t
{
    struct btreenode_t* pbtnl; // 二叉树 左子节点(树结构中视为子节点)
    struct btreenode_t* pbtnr; // 二叉树 右子节点(树结构中视为兄弟节点)
    struct btreenode_t* pbtnp; // 二叉树 父节点,用于 遍历二叉树 (Traversal in Binary Tree),不使用栈或递归(树结构中全部链接到父节点))
    unsigned char       data[];// 数据
}btreenode_t;

/**
 * @brief 获取节点的数据地址
 * 
 */
#define BtreeNodeData(pbtn) (pbtn)->data  

/**
 * @brief 定义 预分配的 btreenode_t* 块指针
 * 
 */
#define btreeblock_t btreenode_t*

#define BTREEDEFAULTCNTBLOCK 32 // 默认分配的 btreeblock_t 块大小,
/**
 * @brief 二叉树
 * 
 */
typedef struct btree_t
{
    btreenode_t*    pbtnRoot;     //二叉树的 root,默认有一个根节点
    btreenode_t*    pbtnPrealloc; // 预分配的 btreenode_t 块, 使用 btreenode_t::pbtnr 形成一个链表
    btreeblock_t    pbtb[BTREEDEFAULTCNTBLOCK]; // 保存预分配的块的指针，用于后续 free
    btreeblock_t*   pbtbM;  //当 pbtb 不够用时 malloc一个空间用于保存 预分配的块的指针
    unsigned int    cntPBTBM; // 当前分配的 pbtbM 大小 btreeblock_t
    unsigned int    cntCapacity; // 当前分配的 btreenode_t 节点数量，包括使用的
    unsigned int    cntElem; //当前 二叉树的结点数
    unsigned int    cntGrow; 
    unsigned int    szElem; //数据本身大小
    unsigned int    szNode;     //btreenode_t和数据 向 sizeof(void*)倍数取整 占用的空间
}btree_t;

#define BTREEMAXLEVEL 64 // 二叉数最大层数

/**
 * @brief 遍历二叉树的 iterator
 * @note 不要在栈在分配 btreeiterator_t* 因为会malloc一个栈指针,当栈超出作用域而没有释放这个栈就会造成内存泄漏
 */
typedef struct btreeiterator_t
{
    struct btree_t* pbt; // 遍历的二叉树对象
    // unsigned int level; // 当前二叉数的层级
    unsigned int cntCapacity; //栈当前的容量(能容里 cntCapacity 个 btreenode_t*)
    unsigned int top; // 当栈顶位置
    btreenode_t** pstack; // 用于遍历的二叉数的栈
}btreeiterator_t;

typedef struct BtreeTraversalCallback_t // TreeTraversal的回调函数的第三个参数
{
    btreenode_t*node;
    unsigned int level;
}BtreeTraversalCallback_t;

typedef int (*BtreeTraversalCallback)(void* data, void*params, BtreeTraversalCallback_t *pbttc); // BtreeTraversal的回调函数

/**
 * @brief 申请并初始化一个 btreeiterator_t*
 * 
 * @param pbt 
 * @param pbtn 
 * @return btreeiterator_t* 
 */
btreeiterator_t* BtreeIteratorInit(btree_t* pbt, btreenode_t* pbtn);
/**
 * @brief 注销一个 btreeiterator_t* 
 * 
 * @param pbti 
 * @return btreeiterator_t* 
 */
void BtreeIteratorUninit(btreeiterator_t* pbti);

/**
 * @brief 先序遍历 Preorder Traversal (current-left-right): Visits the node first, then left subtree, then right subtree.
 * 
 * @param pbti 
 * @param op 遍历到节点时需要调用处理的函数,如果函数返回 < 0 表示退出遍历.
 * int(*op)(void* ptr, void* param) ptr 是 btreenode_t::data, param 是参数
 * @return btreeiterator_t* 
 */
btreeiterator_t* BtreeIteratorTraversalPreorder(btreeiterator_t* pbti, BtreeTraversalCallback op, void* param);
/**
 * @brief 中序遍历 Inorder Traversal (left-current-right): Visits left subtree, then the node, then the right subtree.
 * 
 * @param pbti 
 * @param op 遍历到节点时需要调用处理的函数,如果函数返回 < 0 表示退出遍历.
 * int(*op)(void* ptr, void* param) ptr 是 btreenode_t::data, param 是参数
 * @return btreeiterator_t* 
 */
btreeiterator_t* BtreeIteratorTraversalInorder(btreeiterator_t* pbti, BtreeTraversalCallback op, void* param);
/**
 * @brief 后序遍历 Postorder Traversal (left-right-current): Visits left subtree, then right subtree, then the node.
 * 
 * @param pbti 
 * @param op 遍历到节点时需要调用处理的函数,如果函数返回 < 0 表示退出遍历.
 * int(*op)(void* ptr, void* param) ptr 是 btreenode_t::data, param 是参数
 * @return btreeiterator_t* 
 */
btreeiterator_t* BtreeIteratorTraversalPostorder(btreeiterator_t* pbti, BtreeTraversalCallback op, void* param);
/**
 * @brief Level Order Traversal.
 * 
 * @param pbti 
 * @param op 
 * @param param 
 * @return btreeiterator_t* 
 */
btreeiterator_t* BtreeIteratorTraversalLevelorder(btreeiterator_t* pbti, BtreeTraversalCallback op, void* param);

/**
 * @brief 获取 btree_t* 保存 cnt 数据需要使用的内存的大小
 * 
 */
#define BtreeMemUsed(szElem, cnt) sizeof(btree_t) + ((cnt)+1) * roundup((sizeof(btreenode_t) + (szElem)), sizeof(void*))
/**
 * @brief 申请一个 btree_t
 * 
 * @param szElem 
 * @param cnt 
 * @return btree_t* 
 */
btree_t* BtreeMalloc(unsigned int szElem, unsigned int cnt);
/**
 * @brief 注销一个 btree_t
 * 
 * @param pbt 
 */
void BtreeFree(btree_t* pbt);
/**
 * @brief 初始化一个 btree_t
 * 
 * @param pbt 
 * @param szElem 
 * @param cnt 
 * @return btree_t* 
 */
btree_t* BtreeInit(btree_t* pbt, unsigned int szElem, unsigned int cnt);

/**
 * @brief 注销一个 btree_t*,但不包括 btree_t* 本身
 * 
 * @param pbt 
 */
void BtreeUninit(btree_t* pbt);

/**
 * @brief 再次预分配一个块（扩大 btree_t::pbtnPrealloc 空间 ）会自动调用无需直接调用。
 * 
 * @param pbt 
 * @param cnt 
 * @return btreenode_t* 
 */
int BtreeRealloc(btree_t* pbt, unsigned int grow);

/**
 * @brief 获取根节点(根节点默认分配)
 * 
 * @param pbt 
 * @return btreenode_t* 
 */
btreenode_t* BtreeRoot(btree_t* pbt);
/**
 * @brief 
 * 
 * @param node 
 * @return btreenode_t* 
 */
btreenode_t* BtreeNodeParent(btreenode_t* node);
/**
 * @brief 获取左边的节点
 * 
 * @param node 
 * @return btreenode_t* 
 */
btreenode_t* BtreeNodeLeft(btreenode_t* node);
/**
 * @brief 获取右边的节点
 * 
 * @param node 
 * @return btreenode_t* 
 */
btreenode_t* BtreeNodeRight(btreenode_t* node);
/**
 * @brief 设置节点node 左边的值,如果左边本来没有值就分配一个
 * 
 * @param pbt 
 * @param node 
 * @param data 
 * @return btreenode_t* 返回左子节点
 */
btreenode_t* BtreeNodeSetLeft(btree_t* pbt, btreenode_t* node, void* data);
/**
 * @brief 设置节点node 右边的值,如果右边本来没有值就分配一个
 * 
 * @param pbt 
 * @param node 
 * @param data 
 * @return btreenode_t* 返回右子节点
 */
btreenode_t* BtreeNodeSetRight(btree_t* pbt, btreenode_t* node, void* data);

#define BTREE_TRAVERSAL_PREORDER   0 // Preorder Traversal (current-left-right)
#define BTREE_TRAVERSAL_INORDER    1 // Inorder Traversal (left-current-right)
#define BTREE_TRAVERSAL_POSTORDER  2 // Postorder Traversal (left-right-current)
#define BTREE_TRAVERSAL_LEVELORDER 3 // Level Order Traversal
/**
 * @brief 
 * 
 * @param node 
 * @param callback 
 * @param params 
 * @param mode 
 * @return btreenode_t* 
 * @note
 *                 0
 *           1          2
 *        3    4     5     6
 *      7  8  9 10 11 12 13 14
 * Preorder Traversal (current-left-right):  0    1    3    7    8    4    9   10    2    5   11   12    6   13   14 
 * Inorder Traversal (left-current-right):   7    3    8    1    9    4   10    0   11    5   12    2   13    6   14 
 * Postorder Traversal (left-right-current): 7    8    3    9   10    4    1   11   12    5   13   14    6    2    0 
 * Level Order Traversal:                    0    1    2    3    4    5    6    7    8    9   10   11   12   13   14
 */
btreenode_t* BtreeTraversal(btreenode_t* node, int (*callback)(void* data,void* params), void* params, int mode);

/************************* tree_t 树结构数据 *************************/
/**
 * @brief 获取 需要使用的内存的大小
 * 
 */
#define TreeMemUsed(szElem, cnt) BtreeMemUsed((szElem),(cnt))

/**
 * @brief 树结构
 */
typedef btree_t tree_t;
/**
 * @brief 树结构的结点 pbtnl: 子节点，pbtnr:父节点
 * 
 */
typedef btreenode_t treenode_t;
/**
 * @brief 获取节点的数据地址
 * 
 */
#define TreeNodeData(pbtn) (pbtn)->data  
/**
 * @brief 创建一个 tree_t*
 * 
 * @param szElem 
 * @param cnt 
 * @return tree_t* 
 */
tree_t* TreeMalloc(unsigned int szElem, unsigned int cnt);
/**
 * @brief free 一个 tree_t*
 * 
 * @param pt 
 */
void TreeFree(tree_t* pt);
/**
 * @brief 初始化一个 tree_t*
 * 
 * @param pt 
 * @param szElem 
 * @param cnt 
 * @return tree_t* 
 */
tree_t* TreeInit(tree_t* pt, unsigned int szElem, unsigned int cnt);
/**
 * @brief free tree_t* pt 中的内容,但不包括 tree_t* pt
 * 
 * @param pt 
 */
void TreeUninit(tree_t* pt);
/**
 * @brief 分配一个块给 tree_t*
 * 
 * @param pt 
 * @param cnt 
 * @return int
 */
int TreeRealloc(tree_t* pt, unsigned int cnt);
/**
 * @brief 获取 tree_t* pt 的根结点
 * 
 * @param pt 
 * @return treenode_t* 
 */
treenode_t* TreeRoot(tree_t* pt);

treenode_t* TreeNodeParent(treenode_t* node);
/**
 * @brief 获取节点的第一个子节点
 * 
 * @param node 
 * @return treenode_t* 
 */
treenode_t* TreeNodeChild(treenode_t* node);
/**
 * @brief 获取节点的右边的兄弟节点
 * 
 * @param node 
 * @return treenode_t* 
 */
treenode_t* TreeNodeNext(treenode_t*node);  
treenode_t* TreeNodePrev(treenode_t*node);
/**
 * @brief 设置节点的数据
 * 
 * @param node 
 * @param data 
 * @return treenode_t* 
 */
treenode_t* TreeNodeSet(tree_t* pt, treenode_t*node, void* data);
/**
 * @brief 创建一个节点,数据为 data
 * 
 * @param pt 
 * @param data 
 * @return treenode_t* 
 */
treenode_t* TreeNodeCreate(tree_t* pt, void* data);
/**
 * @brief 删除并回收 node 及其子节点
 * 
 * @param pt 
 * @param node 
 */
void TreeNodeDel(tree_t* pt, treenode_t* node);

/**
 * @brief 给node节点的子节点尾部添加一个子节点,数据为 data
 * 
 * @param pt 
 * @param node 
 * @param data 
 * @return treenode_t* 
 */
treenode_t* TreeNodeAddChild(tree_t* pt, treenode_t* node, treenode_t* child);
treenode_t* TreeNodeAddChild2(tree_t* pt, treenode_t* node, void* data);
/**
 * @brief 给节点添加cnt个子节点,数据为 data
 * 
 * @param pt 
 * @param node 
 * @param data 
 * @param cnt 
 * @return treenode_t* 
 */
treenode_t* TreeNodeAddChildren(tree_t* pt, treenode_t* node, void* data, unsigned int cnt);
/**
 * @brief 给node节点前添加一个兄弟节点,数据为 data
 * 
 * @param pt 
 * @param node 
 * @param data 
 * @return treenode_t* 
 */
treenode_t* TreeNodeInsertBefore(tree_t* pt, treenode_t* node, treenode_t* brother);
/**
 * @brief 给节点添加cnt个兄弟节点,数据为 data
 * 
 * @param pt 
 * @param node 
 * @param data 
 * @param cnt 
 * @return treenode_t* 
 */
treenode_t* TreeNodeAddBrothers(tree_t* pt, treenode_t* node, void* data, unsigned int cnt);

typedef struct TreeTraversalCallback_t // TreeTraversal的回调函数的第三个参数
{
    treenode_t*node;
    unsigned int level;
}TreeTraversalCallback_t;

typedef int (*TreeTraversalCallback)(void* data, void*params, TreeTraversalCallback_t *pttc); // TreeTraversal的回调函数
/**
 * @brief 使用level order traversal 方式 遍历所有节点
 * 
 * @param node 
 * @param callback 
 * @param param 
 * @return int 
 * @note 回调函数 typedef int (*TreeTraversalCallback)(void* data, void*params, TreeTraversalCallback_t *pttc)
 * data 节点的数据本身
 * params 通过 TreeTraversal 参数 params 传递过来的参数
 * 
 */
treenode_t* TreeTraversal( treenode_t* node, TreeTraversalCallback callback, void* params );

#endif // end of define _HEAD_TREE_


